package learn;

public class mergeSort {
    static int[] temp;

    public static void main(String[] args) {
        int[] arr={7,3,6,8,4,11,2,5,7,5,10,40,10,31,23,43,65,12,4,5};
        temp=new int[arr.length];
        System.out.println("排序前");
        show(arr);
        merge_sort(arr,0,arr.length-1,1);
        System.out.println("\n排序后:");
        show(arr);
        //归为两半，各自有序,再排序
    }
    static void show(int[] arr){
        for(int i=0;i<=arr.length-1;i++) System.out.print(arr[i]+" ");
    }
    static void merge_sort(int[] arr,int l,int r,int count){
        if(l>=r)return;
        //归为两半
        int mid=l+r>>1;
        merge_sort(arr,l,mid,2);
        merge_sort(arr,mid+1,r,2);
        if(count==1)show(arr);
        int k=0,i=0,j=mid+1;
        while(i<=mid&&j<=r){
            if(arr[i]<=arr[j])temp[k++]=arr[i++];
            else temp[k++]=arr[j++];
        }
        while(i<=mid)temp[k++]=arr[i++];
        while(j<=r)temp[k++]=arr[j++];
        //复原
     for(i=l,j=0;i<=r;i++,j++)arr[i]=temp[j];
    }
}
//import java.util.Scanner;
//
//public class mergeSort {
//    static int[] arr;
//
//    static int n;
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextInt();
//        arr=new int[n];
//        temp=new int[n];
//        for (int i = 0; i < n; i++) {
//            arr[i] = sc.nextInt();
//        }
//        mergeSort(arr, 0, n - 1);
//        for(int i=0;i<n;i++){
//            System.out.print(arr[i]+" ");
//        }
//    }
//
//    static void mergeSort(int[] arr, int l, int r) {
//        //递归，各种排好返回
//        int mid = (l + r) >> 1;
//        mergeSort(arr, l, mid);
//        mergeSort(arr, mid + 1, r);
//        int k = 0, i = l, j = mid + 1;
//        while (i <= mid && j <= r) {
//            if (arr[i] < arr[j]) temp[k++] = arr[j++];
//            else temp[k++] = arr[i++];
//        }
//        while (i <= mid) temp[k++] = arr[i++];
//        while (j <= r) temp[k++] = arr[j];
//        for (i = l, j = 0; i <= r; i++, j++) {
//            arr[i] = temp[j];
//        }
//
//    }
//
//}